package com.yequan.leetcode.map.groupAnagrams_49;

import java.util.*;

/**
 * @author : Administrator
 * @date : 2020/3/22
 */
public class RecodeGroupAnagrams {

    /**
     * 排序法
     * 1.遍历字符串数组,对每一个字符串数组进行排序
     * 2.用排序后的字符串当做key,原字符串作为值存入map中
     * <p>
     * 复杂度:
     * 时间复杂度: O(N*Log K)
     * 空间复杂度: O(N*K)
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String, List> res = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!res.containsKey(key)) {
                res.put(key, new ArrayList());
            }
            res.get(key).add(str);
        }
        return new ArrayList(res.values());
    }

    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List> res = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!res.containsKey(key)) {
                res.put(key, new ArrayList());
            }
            res.get(key).add(str);
        }
        return new ArrayList(res.values());
    }

    public List<List<String>> groupAnagrams3(String[] strs) {
        Map<String, List> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            map.get(key).add(str);
        }
        return new ArrayList(map.values());
    }

    public List<List<String>> groupAnagrams4(String[] strs) {
        Map<String, List> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            map.get(key).add(str);
        }
        return new ArrayList(map.values());
    }

    public List<List<String>> groupAnagrams5(String[] strs) {
        Map<String, List> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            map.get(key).add(str);
        }
        return new ArrayList(map.values());
    }

}
